Most previous studies focus on the independent cascade (IC) model under the edge-level feedback.

We thank the reviewers for the valuable comments and discussions. Thissettingwas originallyproposedin the6 seminal work by Kempe et al. [19], and most follow-up studies adopt this particular setup (e.g. Therefore,12 our online influence maximization (OIM) is directly on the classical LT model, turning model parameters13 w(e) to be unknown (but fixed) and to be learned in an iterative manner. This is in parallel to the OIM for14 IC model [11,43,45], which also learns unknown edge probability parameters.15 Per ourabove16 discussion, we first want to clarify that the threshold on each node is not a model parameter of the classical17 LT model and our work is a frequentist approach for the onlinesetting.

Most previous studies focus on the independent cascade (IC) model under the edge-level feedback.

Most previous studies focus on the independent cascade (IC) model under the edge-level feedback.

We thank the reviewers for the valuable comments and discussions. Please find our clarifications below. IC model [11,43,45], which also learns unknown edge probability parameters. It is interesting that the reviewer brought up the frequentist versus Bayesian view on OIM-LT. LT model and our work is a frequentist approach for the online setting.

In this survey, we offer an extensive overview of the Online Influence Maximization (IM) problem by covering both theoretical aspects and practical applications. For the integrity of the article and because the online algorithm takes an offline oracle as a subroutine, we first make a clear definition of the Offline IM problem and summarize those commonly used Offline IM algorithms, which include traditional approximation or heuristic algorithms and ML-based algorithms. Then, we give a standard definition of the Online IM problem and a basic Combinatorial Multi-Armed Bandit (CMAB) framework, CMAB-T. Here, we summarize three types of feedback in the CMAB model and discuss in detail how to study the Online IM problem based on the CMAB-T model. This paves the way for solving the Online IM problem by using online learning methods. Furthermore, we have covered almost all Online IM algorithms up to now, focusing on characteristics and theoretical guarantees of online algorithms for different feedback types. Here, we elaborately explain their working principle and how to obtain regret bounds. Besides, we also collect plenty of innovative ideas about problem definition and algorithm designs and pioneering works for variants of the Online IM problem and their corresponding algorithms. Finally, we encapsulate current challenges and outline prospective research directions from four distinct perspectives.

We study the online influence maximization (OIM) problem in social networks, where the learner repeatedly chooses seed nodes to generate cascades, observes the cascade feedback, and gradually learns the best seeds that generate the largest cascade in multiple rounds. In the demand of the real world, we work with node-level feedback instead of the common edge-level feedback in the literature. The edge-level feedback reveals all edges that pass through information in a cascade, whereas the node-level feedback only reveals the activated nodes with timestamps. The node-level feedback is arguably more realistic since in practice it is relatively easy to observe who is influenced but very difficult to observe from which relationship (edge) the influence comes. Previously, there is a nearly optimal $\tilde{O}(\sqrt{T})$-regret algorithm for OIM problem under the linear threshold (LT) diffusion model with node-level feedback. It remains unknown whether the same algorithm exists for the independent cascade (IC) diffusion model. In this paper, we resolve this open problem by presenting an $\tilde{O}(\sqrt{T})$-regret algorithm for OIM problem under the IC model with node-level feedback.

Online influence maximization aims to maximize the influence spread of a content in a social network with unknown network model by selecting a few seed nodes. Recent studies followed a non-adaptive setting, where the seed nodes are selected before the start of the diffusion process and network parameters are updated when the diffusion stops. We consider an adaptive version of content-dependent online influence maximization problem where the seed nodes are sequentially activated based on real-time feedback. In this paper, we formulate the problem as an infinite-horizon discounted MDP under a linear diffusion process and present a model-based reinforcement learning solution. Our algorithm maintains a network model estimate and selects seed users adaptively, exploring the social network while improving the optimal policy optimistically. We establish $\widetilde O(\sqrt{T})$ regret bound for our algorithm. Empirical evaluations on synthetic network demonstrate the efficiency of our algorithm.

We propose a detailed analysis of the online-learning problem for Independent Cascade (IC) models under node-level feedback. These models have widespread applications in modern social networks. Existing works for IC models have only shed light on edge-level feedback models, where the agent knows the explicit outcome of every observed edge. Little is known about node-level feedback models, where only combined outcomes for sets of edges are observed; in other words, the realization of each edge is censored. This censored information, together with the nonlinear form of the aggregated influence probability, make both parameter estimation and algorithm design challenging. We establish the first confidence-region result under this setting. We also develop an online algorithm achieving a cumulative regret of $\mathcal{O}( \sqrt{T})$, matching the theoretical regret bound for IC models with edge-level feedback.